package listStudy;

import common.utils.ListNode;

public class ListStudy04 {

    /**
     * 删除链表中重复的结点
     * 在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。
     * 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5
     * @param args
     */
    public static void main(String[] args) {
        ListNode pHead = new ListNode(1);
        pHead.next = new ListNode(2);
        ListNode temp = pHead.next;
        temp.next = new ListNode(3);
        temp = temp.next;
        temp.next = new ListNode(3);
        temp = temp.next;
        temp.next = new ListNode(4);
        temp = temp.next;
        temp.next = new ListNode(4);
        temp = temp.next;
        temp.next = new ListNode(5);
        temp = temp.next;
        temp.next = new ListNode(5);
        deleteDuplication(pHead);
    }

    /**
     * 删除重复元素，把所有重复的元素均删除
     * @param pHead
     * @return
     */
    public static ListNode deleteDuplication(ListNode pHead){
        if (pHead == null){
            return null;
        }
        ListNode p = new ListNode(0);
        p.next = pHead;
        ListNode q = pHead;
        pHead = p;
        while (q.next != null){
            ListNode temp = q.next;
            //存在相等，找到最后一个不为val的节点或者最后一个节点
            while (temp!= null && temp.val == q.val){
                temp = temp.next;
            }
            if (temp == null){
                p.next = temp;
            } else if (temp != q.next){
                q = temp;
                p.next = q;
            } else {
                p = q;
                q = q.next;
            }
        }
        return pHead.next;
    }
}
